package stack;

import java.util.Stack;

public class P84 {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= len; i++) {
            if (i != len && (stack.isEmpty() || heights[stack.peek()] <= heights[i])) {
                stack.push(i);
            } else if (!stack.isEmpty()) {
                int idx = stack.pop();
                int times = (i - idx); //右侧已经弹出的数量
                if (stack.isEmpty()) {

                    times += idx;
                } else {
                    while (!stack.isEmpty() && heights[stack.peek()] == heights[idx]) {
                        stack.pop();
                        times++;
                    }
                }
                max = Math.max(max, times * heights[idx]);
                System.out.println(times * heights[idx]);
                i--;
            } else {
                break;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        new P84().largestRectangleArea(new int[]{4, 2, 0, 3, 2, 5});
    }
}
